﻿/*
7-37 整数分解为若干项之和 (20 分)
将一个正整数N分解成几个正整数相加，可以有多种分解方法，例如7=6+1，7=5+2，7=5+1+1，…。编程求出正整数N的所有整数分解式子。

输入格式：
每个输入包含一个测试用例，即正整数N (0<N≤30)。

输出格式：
按递增顺序输出N的所有整数分解式子。递增顺序是指：对于两个分解序列N
​​ 序列之前输出。每个式子由小到大相加，式子间用分号隔开，且每输出4个式子后换行。

输入样例：
7
输出样例：
7=1+1+1+1+1+1+1;7=1+1+1+1+1+2;7=1+1+1+1+3;7=1+1+1+2+2
7=1+1+1+4;7=1+1+2+3;7=1+1+5;7=1+2+2+2
7=1+2+4;7=1+3+3;7=1+6;7=2+2+3
7=2+5;7=3+4;7=7
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
	int value;
	int group;
	int cache[30];
	int n;
} Factor, * PFactor;

static void resolve(int value, PFactor factors, int index);

static void print_cache(PFactor factor, int level) {
	factor->n++;
	if (factor->n > 1)
		printf(";");
	printf("%d=%d", factor->value, factor->cache[0]);
	for (int i = 1; i <= level; i++)
		printf("+%d", factor->cache[i]);
	if (factor->n == factor->group) {
		factor->n = 0;
		printf("\n");
	}
}

void resolve(int value, PFactor factor, int level)
{
	int prev = 1;
	if (value == 1) {
		factor->cache[level] = 1;
		print_cache(factor, level);
	}
	else if (value > 1) {
		if (level > 0)prev = factor->cache[level - 1];
		for (int i = prev; i <= value / 2; i++) {
			factor->cache[level] = i;
			resolve(value - i, factor, level + 1);
		}
		factor->cache[level] = value;
		print_cache(factor, level);
	}
}

int main() {
	freopen("D:/Develop/GitRepos/MOOC/浙江大学/数据结构/201906/zju_C_Basic/data/7.37.txt", "r", stdin);
	int n=0;
	scanf("%d", &n);
	Factor factor = {n, 4};
	resolve(n, &factor, 0);
	return 0;
}